package com.yahoo.labs.snow.solver;

import it.unimi.dsi.fastutil.ints.IntOpenHashSet;

import java.util.Random;

import com.yahoo.labs.snow.ProblemInstance;

/**
 * Iteratively picks random pivots, builds a good snowflake around each pivot, then picks another pivot.
 * 
 * Members of past bundles can not be new pivots.
 * 
 * @author chato
 *
 */
public class RandomSOBOSolver extends SnowflakesOneByOneSolver {

	final Random random;

	public RandomSOBOSolver(ProblemInstance problem) {
		super(problem);
		random = new Random(1); // Fixed random seed for reproducibility
		SNOWFLAKE_MEMBERS_CAN_BE_PIVOTS = false;
	}
	
	@Override
	int getPivot(IntOpenHashSet pivotsUsed, IntOpenHashSet possiblePivots) {
		int pivot = randomNode(random);
		while (pivotsUsed.contains(pivot) || (! possiblePivots.contains(pivot)) ) {
			pivot = randomNode(random);
		}
		return pivot;
	}
	
	protected int randomNode(Random aRandom) {
		return aRandom.nextInt(problem.numNodes());
	}
}
